package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: data_structures_algorithms
 * @description:
 * @author: lld
 * @create: 2021-04-23 11:11
 **/
public class Demo3 {
    public static void main(String[] args) {
        Demo3 demo3 = new Demo3();
        int[] arr={2,3,4,5,7,8};
        List<Integer> list = demo3.largestDivisibleSubset(arr);
        System.out.println("list = " + list);
    }
    public List<Integer> largestDivisibleSubset(int[] nums) {
        //先对数组排序
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        int[] prev = new int[nums.length];
        //初始化数组dp的每个值为1
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        int max = 1;//记录最大整除子集的长度
        int maxIndex = 0;//记录最大整除子集中最后一个元素的位置
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                //这里大于号我们改为求余
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    //说明nums[i]可以放到nums[j]后面构成一个更长的整除子集,
                    //也就是[……，……，……，nums[j]，nums[i]]。注意dp[i]记录
                    //的整除子集中，nums[i]一定是数组的最后一个元素，我们用prev[i]
                    //来记录这个子集中nums[i]的前一个元素的位置，也就是nums[j]的位置
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            //如果找到更大的子集，就记录最大的即可
            if (dp[i] > max) {
                max = dp[i];
                maxIndex = i;
            }
        }
        //把找到的最大整除子集加入到list中，prev很类似于链表，每一个都是记录
        //前一个的位置
        List<Integer> res = new ArrayList<>();
        while (maxIndex != -1) {
            res.add(nums[maxIndex]);
            maxIndex = prev[maxIndex];
        }
        return res;
    }

}
